package com.ztom.top100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 多数元素
 * <p>
 * https://leetcode-cn.com/problems/majority-element/
 *
 * @author ZhangTao
 */
public class Code57MajorityElement {

    /**
     * 计数法
     *
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int count = map.getOrDefault(num, 0) + 1;
            if (count > n / 2) {
                return num;
            }
            map.put(num, count);
        }
        return 0;
    }

    /**
     * 排序法
     *
     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length / 2];
    }

    private void quickSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int num = nums[l + ((int) (Math.random() * (r - l + 1)))];
        int[] mid = partition(nums, l, r, num);
        quickSort(nums, l, mid[0] - 1);
        quickSort(nums, mid[1] + 1, r);
    }

    private int[] partition(int[] nums, int l, int r, int num) {
        if (l == r) {
            return new int[]{l, r};
        }
        int less = -1;
        int more = r + 1;
        int index = 0;
        while (index < more) {
            if (nums[index] == num) {
                index++;
            } else if (nums[index] < num) {
                swap(nums, index++, ++less);
            } else {
                swap(nums, index, --more);
            }
        }
        return new int[]{++less, --more};
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    /**
     * 摩尔投票法
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 分别从[0, n - ]位置开始
        // 遇到相同的数+1, 遇到不同的数-1
        // count = 0 时, 从下一个位置继续
        int count = 1;
        int maj = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == maj) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    maj = nums[i + 1];
                }
            }
        }
        return maj;
    }
}
